#define _CRT_SECURE_NO_WARNINGS


//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n;
//int q[N];
//
//int mid_num(int* a, int l, int r)
//{
//    int mid = (l + r) >> 1;
//    if (a[l] > a[r])
//    {
//        if (a[r] > a[mid]) return r;
//        else if (a[l] < a[mid]) return l;
//        else return mid;
//    }
//    else
//    {
//        if (a[l] > a[mid]) return l;
//        else if (a[r] < a[mid]) return r;
//        else return mid;
//    }
//}
//
//void quick_sort(int* a, int l, int r)
//{
//    if (l >= r) return;
//
//    int mid = mid_num(a, l, r);
//    swap(a[mid], a[l]);
//    int x = a[l], i = l - 1, j = r + 1;
//    while (i < j)
//    {
//        do i++; while (a[i] < x);
//        do j--; while (a[j] > x);
//        if (i < j) swap(a[i], a[j]);
//    }
//
//    quick_sort(a, l, j);
//    quick_sort(a, j + 1, r);
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> q[i];
//
//    quick_sort(q, 0, n - 1);
//
//    for (int i = 0; i < n; i++) cout << q[i] << ' ';
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, k;
//int q[N];
//
//int quick_sort(int* a, int l, int r, int k)
//{
//    if (l >= r) return a[l];
//
//    int x = a[(l + r) >> 1], i = l - 1, j = r + 1;
//    while (i < j)
//    {
//        do i++; while (a[i] < x);
//        do j--; while (a[j] > x);
//        if (i < j) swap(a[i], a[j]);
//    }
//
//    int sl = j - l + 1;
//    if (sl >= k) return quick_sort(a, l, j, k);
//    else return quick_sort(a, j + 1, r, k - sl);
//}
//
//int main()
//{
//    cin >> n >> k;
//    for (int i = 0; i < n; i++) cin >> q[i];
//
//    cout << quick_sort(q, 0, n - 1, k) << endl;
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n;
//int q[N], tmp[N];
//
//void merge_sort(int* a, int l, int r)
//{
//    if (l >= r) return;
//
//    int mid = (l + r) >> 1;
//
//    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
//
//    int k = 0, i = l, j = mid + 1;
//    while (i <= mid && j <= r)
//    {
//        if (a[i] < a[j]) tmp[k++] = a[i++];
//        else tmp[k++] = a[j++];
//    }
//
//    while (i <= mid) tmp[k++] = a[i++];
//    while (j <= r) tmp[k++] = a[j++];
//
//    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> q[i];
//
//    merge_sort(q, 0, n - 1);
//
//    for (int i = 0; i < n; i++) cout << q[i] << ' ';
//    cout << endl;
//
//    return 0;
//}

//
//
//#include <iostream>
//using namespace std;
//
//typedef long long LL;
//const int N = 100010;
//int n;
//int q[N], tmp[N];
//
//LL merge_sort(int l, int r)
//{
//    if (l >= r) return 0;
//
//    int mid = (l + r) >> 1;
//
//    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
//
//    int k = 0, i = l, j = mid + 1;
//    while (i <= mid && j <= r)
//    {
//        if (q[i] <= q[j]) tmp[k++] = q[i++];
//        else
//        {
//            res += mid - i + 1;
//            tmp[k++] = q[j++];
//        }
//    }
//
//    while (i <= mid) tmp[k++] = q[i++];
//    while (j <= r) tmp[k++] = q[j++];
//
//    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//
//    return res;
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> q[i];
//
//    cout << merge_sort(0, n - 1) << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, q;
//int a[N];
//
//int main()
//{
//    cin >> n >> q;
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    while (q--)
//    {
//        int k;
//        cin >> k;
//        int l = 0, r = n - 1;
//        while (l < r)
//        {
//            int mid = (l + r) >> 1;
//            if (a[mid] >= k) r = mid;
//            else l = mid + 1;
//        }
//        if (a[l] != k) cout << "-1 -1" << endl;
//        else
//        {
//            cout << l << ' ';
//            l = 0, r = n - 1;
//            while (l < r)
//            {
//                int mid = (l + r + 1) >> 1;
//                if (a[mid] <= k) l = mid;
//                else r = mid - 1;
//            }
//            cout << l << endl;
//        }
//    }
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//double n;
//
//int main()
//{
//    cin >> n;
//    double l = -10000, r = 10000;
//    while (r - l > 1e-8)
//    {
//        double mid = (l + r) / 2;
//        if (mid * mid * mid >= n) r = mid;
//        else l = mid;
//    }
//
//    printf("%lf", l);
//
//    return 0;
//}


//
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//vector<int> add(vector<int>& A, vector<int>& B)
//{
//    vector<int> C;
//
//    int tmp = 0;
//    for (int i = 0; i < A.size() || i < B.size() || tmp; i++)
//    {
//        if (i < A.size()) tmp += A[i];
//        if (i < B.size()) tmp += B[i];
//        C.push_back(tmp % 10);
//        tmp /= 10;
//    }
//
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a, b;
//    vector<int> A, B;
//    cin >> a >> b;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
//
//    auto C = add(A, B);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//
//    return 0;
//}

//
//#include <iostream>
//#include <vector>
//using namespace std;
//
//bool cmp(vector<int>& A, vector<int>& B)
//{
//    if (A.size() != B.size()) return A.size() > B.size();
//    for (int i = A.size() - 1; i >= 0; i--)
//        if (A[i] != B[i]) return A[i] > B[i];
//
//    return true;
//}
//
//vector<int> sub(vector<int>& A, vector<int>& B)
//{
//    vector<int> C;
//
//    int tmp = 0;
//    for (int i = 0; i < A.size(); i++)
//    {
//        tmp = A[i] - tmp;
//        if (i < B.size()) tmp -= B[i];
//        C.push_back((tmp + 10) % 10);
//        if (tmp < 0) tmp = 1;
//        else tmp = 0;
//    }
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a, b;
//    vector<int> A, B;
//    cin >> a >> b;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
//
//    if (cmp(A, B))
//    {
//        auto C = sub(A, B);
//        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//        cout << endl;
//    }
//    else
//    {
//        auto C = sub(B, A);
//        cout << '-';
//        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//        cout << endl;
//    }
//
//    return 0;
//}

//
//#include <iostream>
//#include <vector>
//using namespace std;
//
//vector<int> mul(vector<int>& A, int b)
//{
//    vector<int> C;
//
//    int tmp = 0;
//    for (int i = 0; i < A.size() || tmp; i++)
//    {
//        if (i < A.size()) tmp += A[i] * b;
//        C.push_back(tmp % 10);
//        tmp /= 10;
//    }
//
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a;
//    int b;
//    cin >> a >> b;
//    vector<int> A;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//
//    auto C = mul(A, b);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    cout << endl;
//
//    return 0;
//}


//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//vector<int> div(vector<int>& A, int b, int& r)
//{
//    vector<int> C;
//    for (int i = A.size() - 1; i >= 0; i--)
//    {
//        r = r * 10 + A[i];
//        C.push_back(r / b);
//        r %= b;
//    }
//
//    reverse(C.begin(), C.end());
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a;
//    int b, r = 0;
//    cin >> a >> b;
//    vector<int> A;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//
//    auto C = div(A, b, r);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    cout << endl << r << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], s[N];
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
//
//    while (m--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << s[r] - s[l - 1] << endl;
//    }
//
//    return 0;
//}

//
//
//#include <iostream>
//using namespace std;
//
//const int N = 1010;
//int n, m, q;
//int a[N][N], s[N][N];
//
//int main()
//{
//    cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> a[i][j];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
//
//    while (q--)
//    {
//        int x1, y1, x2, y2;
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
//    }
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], b[N];
//
//void insert(int l, int r, int c)
//{
//    b[l] += c;
//    b[r + 1] -= c;
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
//
//    while (m--)
//    {
//        int l, r, c;
//        cin >> l >> r >> c;
//        insert(l, r, c);
//    }
//
//    for (int i = 1; i <= n; i++) b[i] += b[i - 1];
//    for (int i = 1; i <= n; i++) cout << b[i] << ' ';
//    cout << endl;
//
//    return 0;
//}

//
//
//#include <iostream>
//using namespace std;
//
//const int N = 1010;
//int n, m, q;
//int a[N][N], b[N][N];
//
//void insert(int x1, int y1, int x2, int y2, int c)
//{
//    b[x1][y1] += c;
//    b[x2 + 1][y1] -= c;
//    b[x1][y2 + 1] -= c;
//    b[x2 + 1][y2 + 1] += c;
//}
//
//int main()
//{
//    cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> a[i][j];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            insert(i, j, i, j, a[i][j]);
//
//    while (q--)
//    {
//        int x1, y1, x2, y2, c;
//        cin >> x1 >> y1 >> x2 >> y2 >> c;
//        insert(x1, y1, x2, y2, c);
//    }
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//            cout << b[i][j] << ' ';
//        cout << endl;
//    }
//
//    return 0;
//}

//
//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n;
//int a[N], tmp[N];
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    int max_len = 0;
//    for (int i = 0, j = 0; i < n; i++)
//    {
//        tmp[a[i]] ++;
//        while (tmp[a[i]] > 1) tmp[a[j]] --, j++;
//        max_len = max(max_len, i - j + 1);
//    }
//
//    cout << max_len << endl;
//
//    return 0;
//}


//
//#include <iostream>
//#include <unordered_map>
//using namespace std;
//
//const int N = 100010;
//int n, m, x;
//int a[N], b[N];
//
//int main()
//{
//    unordered_map<int, int> mp;
//    cin >> n >> m >> x;
//    for (int i = 0; i < n; i++) cin >> a[i], mp[a[i]] = i;
//    for (int i = 0; i < m; i++) cin >> b[i];
//
//    for (int i = 0; i < m; i++)
//    {
//        int targe = x - b[i];
//        if (mp.count(targe))
//        {
//            cout << mp[targe] << ' ' << i << endl;
//            break;
//        }
//    }
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], b[N];
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 0; i < n; i++) cin >> a[i];
//    for (int i = 0; i < m; i++) cin >> b[i];
//
//    int l1 = 0, l2 = 0;
//    while (l1 < n && l2 < m)
//    {
//        while (l2 < m && b[l2] != a[l1]) l2++;
//        if (l2 == m) break;
//        l1++;
//        l2++;
//    }
//
//    if (l1 == n || (l1 == n && l2 == m)) cout << "Yes" << endl;
//    else cout << "No" << endl;
//
//    return 0;
//}

//
//
//#include <iostream>
//
//using namespace std;
//int n;
//
//int lowbit(int x)
//{
//    return x & -x;
//}
//
//int main()
//{
//    cin >> n;
//
//    while (n--)
//    {
//        int tmp = 0, count = 0;
//        cin >> tmp;
//        while (tmp) tmp -= lowbit(tmp), count++;
//        cout << count << ' ';
//    }
//    cout << endl;
//
//    return 0;
//}


//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//const int N = 300010;
//int n, m;
//int a[N], s[N];
//vector<int> alls;
//vector<pair<int, int>> xc, lr;
//
//int find(int x)
//{
//    int l = 0, r = alls.size() - 1;
//    while (l < r)
//    {
//        int mid = (l + r) >> 1;
//        if (alls[mid] >= x) r = mid;
//        else l = mid + 1;
//    }
//
//    return l + 1;
//}
//
//vector<int>::iterator my_unique(vector<int>& a)
//{
//    int j = 0;
//    for (int i = 0; i < a.size(); i++)
//    {
//        if (!i || a[i] != a[i - 1])
//            a[j++] = a[i];
//    }
//
//    return a.begin() + j;
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 0; i < n; i++)
//    {
//        int x, c;
//        cin >> x >> c;
//        alls.push_back(x);
//        xc.push_back({ x, c });
//    }
//
//    for (int i = 0; i < m; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        lr.push_back({ l, r });
//        alls.push_back(l);
//        alls.push_back(r);
//    }
//
//    sort(alls.begin(), alls.end());
//    alls.erase(my_unique(alls), alls.end());
//
//    for (auto item : xc)
//    {
//        int i = find(item.first);
//        a[i] += item.second;
//    }
//
//    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
//
//    for (auto item : lr)
//    {
//        int l = find(item.first), r = find(item.second);
//        cout << s[r] - s[l - 1] << endl;
//    }
//
//    return 0;
//}


//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int n;
//vector<pair<int, int>> lr;
//
//void merge(vector<pair<int, int>>& a)
//{
//    vector<pair<int, int>> tmp;
//    sort(a.begin(), a.end());
//
//    int st = -2e9, ed = -2e9;
//    for (auto i : a)
//        if (ed < i.first)
//        {
//            if (st != -2e9) tmp.push_back({ st, ed });
//            st = i.first, ed = i.second;
//        }
//        else ed = max(ed, i.second);
//
//    if (st != -2e9) tmp.push_back({ st, ed });
//
//    a = tmp;
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        lr.push_back({ l, r });
//    }
//
//    merge(lr);
//
//    cout << lr.size() << endl;
//
//    return 0;
//}